#pragma once
#include<vector>
#include <string>



//哈希桶-开散列拉链法

namespace knight
{
	//通过仿函数对K进行处理从而在表中进行映射
	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	//特化 对非整形数据进行处理
	template<>
	struct HashFunc<std::string>
	{
		size_t operator()(const std::string& key)
		{
			//对字符串进行处理
			size_t num = 0;
			for (int i = 0; i < key.size(); i++)
			{
				num += key[i];
				num *= 152;
			}
			return num;
		}
	};

    //哈希表中存储的结点
	template<class T>
	struct HashData
	{
		T _data;
		HashData* _next;
	};

	//哈希表
	template<class K,class T ,class KOFV,class Hash=HashFunc<K>>
	class HashTable
	{
		typedef HashData<T> Node;
	public:
		//构造函数
		HashTable()
			:_num(0)
		{
			_table.resize(10);
		}
		//析构函数
		~HashTable()
		{
			Clear();
		}
		//清理哈希表中的数据
		void Clear()
		{
			for (int i = -0; i < _table.size(); i++)
			{
				if (_table[i])
				{
					Node* cur = _table[i];
					Node* next = cur->_next;
					while (cur)
					{
						delete cur;
						cur = next;
						if (cur)
						{
							next = cur->_next;
						}
					}
					_table[i] = nullptr;
				}
			}
		}
		//插入
		bool insert(const T& data)
		{
			Hash hash;
			KOFV kofv;
			//检查负载因子
			if (_num*10 /_table.size() >= 7)
			{
				//扩容
				std::vector<Node*> newtable;
				size_t newsize = _table.size() * 2;
				newtable.resize(newsize);
				for (int i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while(cur)
					{
						Node* next = cur->_next;
						size_t newindex = hash(kofv(cur->_data)) % _table.size();
						cur->_next = newtable[newindex];
						newtable[newindex] = cur->_next;
						cur = next;
					}
					_table[i] = nullptr;
				}
				_table.swap(newtable);
			}
			//算出映射值
			
			size_t index = hash(kofv(data)) % _table.size();
			Node* cur = _table[index];
			while (cur)
			{
				if (cur->_data = data)
				{
					return false;
				}
				cur = cur->_next;
			}

			//头插
			Node* newnode = new Node(data);
			newnode->_next = _table[index];
			_table[index] = newnode;
			
			//改变计数器
			_num++;
			
			return true;

		}

		bool find(const K& key)
		{
			Hash hash;
			KOFV kofv;
			size_t index = hash(key) % _table.size();
			Node* cur = _table[index];
			while(cur)
			{
				if (kofv(cur->_data) == key)
				{
					return  true;
				}
				else
				{
					cur = cur->_next;
				}
			}
			return false;
		}
		
		bool earse(const K& key)
		{
			Hash hash;
			KOFV kofv;
			size_t index = hash(key) % _table.size();
			Node* cur = _table[index];
			Node* prev = nullptr;
			while(cur)
			{
				if (kofv(cur->_data) == key && prev==nullptr)
				{
					_table[index] = cur->_next;
					delete cur;
					--_num;
					return true;
				}
				else if (kofv(cur->_data) == key && prev != nullptr)
				{
					prev->_next = cur->_next;
					delete cur;
					--_num;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}
	    

	private:
		std::vector<Node*> _table;
		size_t _num = 0;
	};

}
//闭散列实现哈希表

namespace knight1
{
	//哈希表中储存的结点
    enum STATE { EMPTY, EXIST, DELETE };
	template<class K, class V>
	class HashData
	{
		std::pair<K, V>  _kv;
		STATE  _state;

	};
	template<class K, class V>
	class HashTable
	{
		
	public:
	    typedef HashData<K, V> HashData;
		//构造函数
		HashTable(size_t capacity = 10)
			: _ht(capacity), _size(0)
		{
			for (size_t i = 0; i < capacity; ++i)
				_ht[i]._state = EMPTY;
		}
		
		bool insert(const std::pair<K,V>& kv)
		{
			//检查容量
			if (_size * 10 / _ht.size() >= 7)
			{
				//扩容
				size_t newcapacity = _ht.size() * 2;
				std::vector<HashData> _newht(newcapacity);
				for (int i = 0; i < _ht.size(); i++)
				{
					size_t index = _ht[i]._kv.first % newcapacity;
					if (_newht[index]._state == EMPTY)
					{
						_newht[index] = _ht[i];
					}
					else
					{
						while (true)
						{
							index++;
							index %= newcapacity;
							if (_newht[index]._state == EMPTY)
							{
								_newht[index] = _ht[i];
								break;
							}
						}
					}
				}
				_ht, swap(_newht);
				
			}
			//插入
			size_t newindex = kv.first % _ht.size();
			if (_ht[newindex]._state == EMPTY || _ht[newindex]._state == DELETE)
			{
				_ht[newindex]._kv = kv;
				_ht[newindex]._state = EXIST;
			}
			else
			{
				while (true)
				{
					newindex++;
					newindex %= _ht.size();
					if (_ht[newindex]._state == EMPTY || _ht[newindex]._state == DELETE)
					{
						_ht[newindex]._kv = kv;
						_ht[newindex]._state = EXIST;
						break;
					}
				}
			}
			_size++;
			return true;
		}
		
		size_t find(const K& key)
		{
			size_t index = key % _ht.size();
			while (_ht[index]._state != EMPTY)
			{
				if (_ht[index]._kv.first == key && _ht[index]._state == EXIST)
				{
					return index;
				}
				index++;
				index %= _ht.size();
			}
			
			return -1;
			
		}
		
		bool earse(const K& key)
		{
			size_t index = find(key);
			if (index == -1)
			{
				return false;
			}
			_ht[index]._state = DELETE;
			_size--;
			return true;
		}
		
	private:
		std::vector<HashData>  _ht;
		size_t  _size;
		
	};
}